home *** CD-ROM | disk | FTP | other *** search
/ Aminet 45 / Aminet 45 (2001)(GTI - Schatztruhe)[!][Oct 2001].iso / Aminet / dev / src / sort.lha / Insertion_Sort.c < prev    next >
C/C++ Source or Header  |  2001-08-22  |  1KB  |  76 lines
  1. /*
  2. **  Insertion Sort Algorithmus in C
  3. **  Norman Walter, Universität Stuttgart
  4. **  Datum: 22.8.2001
  5. **
  6. **  Eigenschaften: Insertion Sort benötigt im Durchschnitt
  7. **  ungefähr N^2/4 Vergleiche und N^2/8 Austauschoperationen,
  8. **  im ungünstigsten Fall doppelt so viele.
  9. */
  10.  
  11. #include <stdio.h>
  12. #include <stdlib.h>
  13.  
  14. #define maxN 100
  15.  
  16. void display(int a[], int n)
  17. {
  18.  
  19. /* Gibt komplettes Array aus */
  20.  
  21.    int i;
  22.    for (i = 1; i <= n; i++) printf ("%d ", a[i]);
  23.     printf("\n");
  24. }
  25.  
  26. void insertion(int a[], int N)
  27.  
  28. /* Insertion-Sort Algorithmus */
  29. /* Sortieren durch direktes Einfügen */
  30.  
  31.   {
  32.     /* Betrachte die Elemente eines nach dem anderen und füge jedes
  33.     ** an seinen richtigen Platz zwischen den bereits betrachteten
  34.     ** ein, wobei diese sortiert bleiben. Das gerade betrachtete
  35.     ** Element wird eingefügt, indem die größeren Elemente einfach
  36.     ** um eine Position nach rechts bewegt werden und das Element
  37.     ** dann auf dem freigewordenen Platz eingefügt wird.
  38.     */
  39.  
  40.     int i, j, v;
  41.     for (i = 2; i <= N; i++ )
  42.         {
  43.             v = a[i]; j = i;
  44.             while (a[j-1] > v)
  45.                 { a[j] = a[j-1]; j--; }
  46.             a[j] = v;
  47.             display(a,N);
  48.         }
  49.   }
  50.  
  51. int main()
  52.  
  53. {
  54.  
  55. int i;
  56. int n, a[maxN+1];
  57.  
  58. /* Schleife erzeugt zufällige Permutation */
  59.  
  60.   for(n=0; n<=15; n++)
  61.   {
  62.     i = rand() % 10;
  63.     a[n+1] = i;
  64.     printf ("%d ",i);
  65.   }
  66.  
  67. printf("\n");
  68.  
  69. /* Array sortieren */
  70.  
  71. a[0] = 0; insertion(a,n);
  72.  
  73. return(0);
  74.  
  75. }
  76.